# def merge_sort(arr):
#     """归并排序"""
#     if len(arr) == 1:
#         return arr
#     # 使用二分法将数列分两个
#     mid = len(arr) // 2
#     left = arr[:mid]
#     right = arr[mid:]
#     # 使用递归运算
#     return marge(merge_sort(left), merge_sort(right))

# def marge(left, right):
#     """排序合并两个数列"""
#     result = []
#     # 两个数列都有值
#     while len(left) > 0 and len(right) > 0:
#         # 左右两个数列第一个最小放前面
#         if left[0] <= right[0]:
#             result.append(left.pop(0))
#         else:
#             result.append(right.pop(0))
#     # 只有一个数列中还有值，直接添加
#     result += left
#     result += right
#     return result
def merge_sort(nums):
    if len(nums) == 1:
        return nums
    length = len(nums)
    mid = int(length / 2)

    left = nums[:mid]
    right = nums[mid:]
    return sort(merge_sort(left), merge_sort(right))


def sort(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    result +=left

    result +=right
    return result
if __name__=="__main__":
    print(merge_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]))

# 返回结果[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]